public class ListNode {
    static class Node{

        public Node next;
        public int val;

        public Node(int val){
            this.val = val;
        }
    }

    //头节点
    public Node head;

    //打印链表
    public void DisplayList(){
        Node cur = head;
        while(cur!=null){
            System.out.print(cur.val+" ");
            cur = cur.next;
        }
        System.out.println( );
    }

    //头插法加入链表
    public void AddFirst(int data){
        Node node = new Node(data);
        node.next = head;
        head = node;
    }

    //尾插法加入链表
    public void AddLast(int data){
        Node node = new Node(data);
        Node cur = head;
        if(head==null){
            head = node;
        }else{
            while(cur.next!=null){
                cur = cur.next;
            }
            cur.next = node;
        }
    }

    public Node FindIndexSubOfOne(int index){
        Node prev = head;
        while(index-1!=0){
            prev = prev.next;
            index--;
        }
        return prev;
    }

    //找到index下标位置插入
    public void FindIndexAdd(int index,int data){
        Node node = new Node(data);
        if(index==0){
            AddFirst(data);
            return;
        }
        if(index==Size()){
            AddLast(data);
            return;
        }
        //不是头插不是尾插
        Node prev = FindIndexSubOfOne(index);
        node.next = prev.next;
        prev.next = node;
    }

    //找到第一次出现key的前一个结点
    public Node FindSubOfOneKey(int key){
        Node prev = head;
        while(prev.next!=null){
            if(prev.next.val==key){
                return prev;
            }
            prev = prev.next;
        }
        return null;
    }

    //删除第一次出现key的结点
    public void ReMoveKey(int key){
        if(head.val==key){
            head = head.next;
            return;
        }

        Node prev = FindSubOfOneKey(key);
        if(prev==null) return;
        prev.next = prev.next.next;
    }

    //删除所有key
    public void ReMoveAllKey(int key){
        if(head==null) return;
        Node cur = head.next;
        Node prev = head;
        while(cur!=null){
            if(cur.val==key){
                prev.next = cur.next;
                cur = cur.next;
            }else {
                prev = cur;
                cur = cur.next;
            }
        }
        if(head.val==key){
            head = head.next;
        }
    }

    //反转链表
    public Node ReverseList(){
        if(head == null) return null;
        if(head.next==null) return head;
        Node cur = head.next;
        head.next = null;
        while(cur!=null){
            Node curNext = cur.next;
            cur.next = head;
            head = cur;
            cur = curNext;
        }
        return head;
    }

    public void ClearList(){
        this.head = null;
    }

    public int Size(){
        Node cur = head;
        int count = 0;
        while(cur!=null){
            count++;
            cur = cur.next;
        }
        return count;
    }

    public Node MiddleNode(){
        Node fast = head;
        Node slow = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
